The present invention relates to wireless communications and more particularly to a method, system and apparatus for allocating resources in order to improve data throughput of basestations in a wireless network.
As is well known, the use of wireless communications for voice communications is growing at a phenomenal rate. To accommodate this rate of growth, organizations providing wireless communications services have attempted to meet demand by an increased rate of deployment of new basestations (BS) and related infrastructure.
In addition to the growth in the use of wireless communications for voice transmissions, the wireless industry has seen an even faster rate of growth in use of its wireless communications infrastructure for data transmissions. Leading this increase in usage has been data enabled mobilestations (MS) such as the hand-held Palm(trademark) available from Palm Computer Corp. and the i9000(trademark) from Nokia OY. These data enabled mobilestations (which may also have voice capabilities) may transmit data over the wireless network using conventional data protocols such as the Internet and the Wireless Application Protocols (IP and WAP, respectively).
However, despite the tremendous efforts of these organizations to satisfy the demand for bandwidth by their customers, instances of insufficient of data resources in the wireless networks are, unfortunately, all too common. This insufficiency results in longer time periods for a data request to be satisfied resulting in dissatisfied and frustrated users.
In the Time Division Multiple Access (TDMA) wireless regime, the data resources are fixed slices of time, known as timeslots in a TDMA frame, which can be allocated to individual wireless users. The resources allocated to a single individual over a series of frames form a virtual channel between the user""s wireless MS (such as a wireless phone) and the BS.
Unfortunately, for a given time period, the number of TDMA frames, and thus the number of timeslots, that are available for allocation to wireless users is finite and therefore limiting. While the data transfer rate during each timeslot could be increased, an increased data transfer rate is often insufficient to meet the demand for resources by wireless users.
Compounding the problem of a shortage of wireless resources, some wireless service providers have also attempted to provide some users with a guaranteed level or quality of service (QoS). In the providing a guaranteed QoS to some users, the number of resources available to other users without QoS guarantees is diminished for a given time period.
In the past, data resources over a given time period have been allocated amongst wireless users requesting such resources on a xe2x80x9cbest effortxe2x80x9d basis. As persons skilled in the art are aware, some mobilestations have the feature or capacity to transmit and/or receive (i.e. handle) data in more than one timeslot in a given TDMA frame. Moreover, there are various grades or levels to these xe2x80x9chigh capacityxe2x80x9d MSs. That is, at one level or grade, a high capacity MS may be able to handle one timeslot per frame in transmitting data to the BS and handle two timeslots per frame in receiving data from the BS. A next level or grade of high capacity MS may be, for example, able to handle two timeslots per frame in transmitting and receiving data. Additional levels or grades of high capacity MSs may also be defined.
The xe2x80x9cbest effortxe2x80x9d allocation scheme currently employed typically allocates more data resources to those MSs which have the capacity to handle additional timeslots. As will be appreciated, some high capacity MSs may, over a given time period, be allocated less resources than they are capable of handling due to the finite availability of resources. Unfortunately, this xe2x80x9cbest effortxe2x80x9d allocation scheme has proven to be unsatisfactory for a number of reasons. First, the best effort allocation scheme will allocate proportionally more of the available resources to those MSs which have the capacity to handle additional timeslots. However, as will be appreciated by those of ordinary skill in the art, a channel between a high capacity MS and the BS may be of very poor quality. Therefore, the errors received as a result of these poor quality channels will reduce the net data throughput (i.e., the data reliably received by the recipient). As a result, much of the resources or bandwidth allocated to those high capacity MSs which have poor channels with the BS is wasted. This waste of resources may result in other MSs, which could establish a high quality channel but have not been allocated their maximum capacity of resources, having their net data throughput unnecessarily and unduly restricted. As a result, the overall net data throughput of a BS is limited by the allocation of resources to those MS with poor quality channels. Further, since the capacity of each MS is predefined and does not change over time, the best effort scheme is staticxe2x80x94not accounting for changes in properties of the channels between the BS and MSs over time.
Accordingly, a resource allocation scheme is desired which optimizes the overall data throughput of a basestation which allows additional wireless users to be serviced or existing wireless users to be serviced more efficiently without the deployment of additional basestations or an increase in data transfer rate between the mobilestations and the basestation. It is also desirable to employ a resource allocation scheme which is sufficiently flexible to adapt to circumstances where QoS guarantees have been made.
The present invention improves (i.e., increases aggregate) the quantity data transferred between a plurality of MSs and a BS and hence data that is reliably received by the designated recipient (i.e. the corresponding BS or MS) using an improved resource allocation scheme. This resource allocation scheme, unlike previous schemes, takes into account the quality of the channel between each MS and the BS for either or both of uplink (UL) and the downlink (DL) temporary block flows (TBFs). (The UL is the TBF wherein data is transferred from the MS to the BS and the DL is the reverse. TBFs for UL and DL are considered to be distinct transfers.) Conventional linear programming methods may be used to optimize the overall data throughput at the BS by allocating timeslots to a channel between the BS and a MS in accordance with the allocation scheme disclosed.
Advantageously, the resource allocation scheme uses the aggregate throughput which uses the actual reliably received data rates (rather than transmitted data rates) for some TBFs in a given time period to allocate the resources in a subsequent time period. In this manner those channels which are of higher quality and have a higher rates of data transfer are allocated a larger proportion of the resources available. Allocating a larger proportion of resources (i.e., giving priority) to those channels which are of higher quality and have a higher data transfer rate increases the aggregate data transfer rate of the BS. In contrast, conventional basestations may have allocated a larger portion of resources to a channel which had a lower data transfer rate and/or was of lower quality.
Further, since different MSs communicate with a BS at different data rates, the allocation scheme attempts to satisfy resource requests by allocating more resources to those MSs which are of high quality and have a high data transfer with the goal that the resources allocated to these types of channels will result in those MSs terminating their sessions with the BS quickly thus freeing up resources at a later time to the channels that are of low quality and/or have a low data throughput rate. Moreover, in the interim, since the wireless channel is dynamic, the quality and throughput of the these latter channels may have improved. As a result, the overall data throughput of a BS using the allocation scheme of the invention over a long period of time may outperform the conventional BS resource allocation schemes.
The resource scheme of the present invention may be applied to only the UL TBFs; only the DL TBFs; to both the UL and DL TBFs.
In one aspect of the invention there is provided a method of allocating data resources for a plurality of channels, each of said plurality of channels enabling communication between a basestation (BS) and a mobilestation (MS), the method comprising: determining a maximum data transmission, absent any errors, of a basestation for the aggregation of the plurality of channels supported by the basestation based on: the number of the plurality of channels supported by the basestation; a bit rate associated with each of the plurality of channels; and a quantity of data resources to be allocated by the basestation; optimizing an objective function, the objective function equal to the maximum data throughput diminished by a factor corresponding to the quality of at least some of the plurality of channels, the optimizing subject to: all of the data resources being allocated; and each of the plurality of channels being allocated at least a portion of the resources; and allocating the data resources based on the optimizing.
In a further aspect of the invention there is provided a resource allocator in a basestation (BS), the BS forming part of a wireless network, the resource allocator operable to: obtain a number of mobilestations (MS) requiring resources, a quantity of resources available for allocation and a data transfer rate of the channel between each MS and the BS; obtain a quality metric for at least some of the channels between the BS and at least some of the mobilestations; allocate resources available for allocation at the BS based on an optimization of an objective function, the objective function reducing a calculated total data transmission quantity by a quality quantity corresponding to a quantity metric of a least some of the channels between the BS and each MS, the objective function subject to the constraints that the MS be allocated at least a portion of the resources available for allocation and all the resources available be allocated.
In a further aspect of the invention there is provider a method of optimizing allocation of resources for uplink channels between a plurality of mobilestations (MS) and a basestation (BS), each uplink channel corresponding to a channel between one of the plurality of mobilestations and the BS, the method comprising: determining a quality measurement for a portion of the uplink channels; determining an approximate total data able to be transmitted between the plurality of MS and the BS based on a data transfer rate for each channel, the number of the plurality of mobilestations and the quality measurement for a portion of the channels; optimizing an allocation of the wireless resources based on the approximate total data throughput and the constraints that all resources be allocated and that each of the plurality of MS be allocated a portion of the wireless resources available.
In a further aspect of the invention there is provided a a method of allocating timeslots within a current group of timeslots to a plurality of communications channels transported within sequential groups, each of said groups comprising a fixed number of timeslots, said method comprising: allocating a percentage of said fixed number of timeslots to each of said plurality of channels so as to maximize an estimated total number of bits received without error by a recipient within said current group by estimating a number of bits in error for each of said channels for said current group based on a measured number of bits in error for each of said channels in at least one previous group.
In a further aspect of the invention there is provided in a communications system in which a plurality of communications channels are transported in sequential pool of resources having a fixed number of timeslots, a method of allocating timeslots within a current pool of resources to said plurality of communications channels, said method comprising: allocating a percentage of said fixed number of timeslots to each of said plurality of channels so as to improve an estimated overall data throughput of the current pool of resources by: calculating the actual data throughput of a pool of resources of a previous pool of resources; defining an allocation function to be optimized, the allocation function being a function of the quality and data rate of each channel and the percentage such that high quality and high data rate communications channels are allocated a larger percentage of said fixed number of timeslots than communications channels of low quality and low data rates; and wherein each of said plurality communications channels is allocated at least some percentage of said fixed number of timeslots.